package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func pathSum2(root *TreeNode, targetSum int) [][]int {
	if root == nil {
		return nil
	}
	var result [][]int
	sumMap := map[*TreeNode]int{
		root: root.Val,
	}
	pathMap := map[*TreeNode][]int{
		root: {root.Val},
	}
	stack := []*TreeNode{root}
	for len(stack) > 0 {
		top := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		sum := sumMap[top]
		path := pathMap[top]
		if top.Left != nil {
			stack = append(stack, top.Left)
			sumMap[top.Left] = sum + top.Left.Val
			leftPath := make([]int, len(path))
			copy(leftPath, path)
			pathMap[top.Left] = append(leftPath, top.Left.Val)
		}
		if top.Right != nil {
			stack = append(stack, top.Right)
			sumMap[top.Right] = sum + top.Right.Val
			rightPath := make([]int, len(path))
			copy(rightPath, path)
			pathMap[top.Right] = append(rightPath, top.Right.Val)
		}
		if top.Left == nil && top.Right == nil {
			// leaf node
			if sum == targetSum {
				result = append(result, path)
			}
		}
	}
	return result
}

func pathSum(root *TreeNode, targetSum int) [][]int {
    var result [][]int
	var dfs func(root *TreeNode, targetSum int, path *[]int) 
	dfs = func(root *TreeNode, targetSum int, path *[]int) {
		if root == nil {
			return
		}
		(*path) = append((*path), root.Val)
		if root.Left == nil && root.Right == nil && targetSum == root.Val {
			tmp := make([]int, len(*path))
			copy(tmp, *path)
			result = append(result, tmp)
		}
		dfs(root.Left, targetSum - root.Val, path)
		dfs(root.Right, targetSum - root.Val, path)
		(*path) = (*path)[:len(*path)-1]
	}
	dfs(root, targetSum, &[]int{})
	return result
}

func main() {
	root := &TreeNode{
		Val: 5,
		Left: &TreeNode{
			Val: 4,
			Left: &TreeNode{
				Val: 11,
				Left: &TreeNode{
					Val: 7,
				},
				Right: &TreeNode{
					Val: 2,
				},
			},
		},
		Right: &TreeNode{
			Val: 8,
			Left: &TreeNode{
				Val: 13,
			},
			Right: &TreeNode{
				Val: 4,
				Left: &TreeNode{
					Val: 5,
				},
				Right: &TreeNode{
					Val: 1,
				},
			},
		},
	}
	ret := pathSum(root, 22)
	fmt.Printf("%#v\n", ret)
}
